The present invention pertains to the field of computer architecture, and more particularly to a path speculating instruction scheduler.
A computer program, also called software, is executed by a computer system as a series of instructions. An instruction is a command to a processor in the computer system to perform a basic logical or mathematical operation such as an add, a subtract, or a load from memory. A compiler translates source language code of the software into a series of instructions, and then schedules the instructions for execution by the processor. The processor fetches and executes the instructions according to the schedule in what is called an instruction stream.
Operands are required to execute each instruction, and are available as immediate data in the instruction stream or as a result of the execution of another instruction. For example, an instruction stream comprising instructions 51 and 52 may be defined by the following operands:
instruction 51: a=5+3
instruction 52: b=a*9
The instruction 51 has both of its operands, the constant values 5 and 3, immediately available in the instruction stream. However, the operand a for instruction 52 is a result of the execution of instruction 51. An instruction, such as instruction 52, which requires the execution result of another instruction for an operand is referred to as a data dependent instruction or a data successor. An instruction, such as instruction 51, that provides an operand for a data dependent instruction is referred to as a source instruction or a data predecessor.
Conventional computer systems have in-order execution pipelines to execute instructions. An in-order execution processor usually fetches an instruction stream from a memory and executes each instruction in the instruction stream according to a sequential program order. Accordingly, an instruction in an in-order execution processor generally begins execution after the execution of prior instructions in the program order. A delay in the execution of an earlier instruction in the program order can delay the execution of a later instruction. Such delays may have several causes. For example, the earlier instruction may need to wait for an operand to be fetched from an external data storage device. The resulting delay in the beginning of the execution of the later instruction similarly delays the beginning of execution of succeeding instructions in the program order.
Instructions can be scheduled out of order to improve the instruction execution performance of a processor. The instructions may be scheduled out of order according to the availability of resources required to execute each instruction. More particularly, later instructions in a program order that have the resources required for execution available may be scheduled for execution ahead of earlier instructions in the program order. The instruction execution performance of a processor that executes instructions scheduled out of order may be enhanced over in-order execution processors because a delay in the execution of earlier instructions in the program order typically does not delay the execution of later instructions in the program order.
There remains a need for improved methods of scheduling instructions for execution such that a processor may execute the instructions more rapidly.
According to one embodiment of the present invention instructions are placed into a control flow graph having blocks of the instructions, the control flow graph defining a number of paths of control flow through the blocks of instructions. A list of candidate instructions to be scheduled into a target block in the control flow graph for execution is built, and one of the candidate instructions is selected to be scheduled into the target block based on whether a single copy on a path property for the selected instruction in the target block will be maintained or terminated on one or more paths through the target block.
Advantages of the invention will be apparent to one skilled in the art upon an examination of the detailed description.